#include <vector>
#include <unordered_map>
#include <tuple>
#include <cmath>
#include <cstdio>
/***
 * Leetcode #2711
 */


using namespace std;

namespace S1 {
    class Soultion {
    public:
        vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
            int m = grid.size();
            int n = grid[0].size();

            vector<vector<int>> res(m, vector<int>(n));

            int total_diags = m + n - 1;
            vector<vector<tuple<int, int, int>>> diags(total_diags);
            
            // 1. 按照对角线存储元素
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 这是计算一种方式索引
                    int d = i - j;
                    int index = d + n - 1;
                    diags[index].push_back({i, j, grid[i][j]});
                }
            }

            //    计算每条对角线的前缀和后缀不同值    对角线是指的这个
            for(auto& flag : diags) {
                int size = flag.size();
                if (size == 0) continue;
                vector<int> vals;
                for (auto& t : flag) {
                    vals.push_back(get<2>(t)); // 取出值
                }

                // 计算前缀不同值     
                vector<int> pre_diff(size);
                unordered_map<int, int> freq_pre;
                int current_pre = 0;

                for (int i = 0; i < size; i++) {
                    int v = vals[i];
                    if (freq_pre[v]==0) {
                        current_pre++;
                    }
                    freq_pre[v]++;
                    pre_diff[i] = current_pre;
                }
                // 计算后缀不同值
                vector<int> suf_diff(size);
                unordered_map<int, int> freq_suf;
                int current_suf = 0;
                for (int i = size - 1; i >= 0; i--) {
                    int v = vals[i];
                    if (freq_suf[v] == 0) {
                        current_suf++;
                    }
                    freq_suf[v]++;
                    suf_diff[i] = current_suf;
                }
                // 计算结果
                for (int idx = 0; idx < size; idx++) {
                    int i = get<0>(flag[idx]);
                    int j = get<1>(flag[idx]);
                    int left = (idx > 0) ? pre_diff[idx - 1] : 0;
                    int right = (idx < size -1) ? suf_diff[idx + 1] : 0;
                    res[i][j] = abs(left - right);
                }
            }
            return res;
        }
    };
}


int main() {

    S1::Soultion s;
    vector<vector<int>> grid = {{1,2,3},{3,1,5},{3,2,1}};
    auto res = s.differenceOfDistinctValues(grid);

    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            printf("%d ", res[i][j]);
        }
        printf("\n");
    }
    return 0;       
}